#
# @lc app=leetcode.cn id=236 lang=python3
#
# [236] 二叉树的最近公共祖先
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution:
    def ___init__(self):
        self.ans = None

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """递归解法
        1. 从根节点开始遍历树。
        2. 如果当前节点本身是 p 或 q 中的一个，我们会将变量 mid 标记为 true，
            并继续搜索左右分支中的另一个节点。
        3. 如果左分支或右分支中的任何一个返回 true，则表示在下面找到了两个节点中的一个。
        4. 如果在遍历的任何点上，左、右或中三个标志中的任意两个变为 true，
            这意味着我们找到了节点 p 和 q 的最近公共祖先。
        """
        # 出口
        if not root or root == p or root == q:
            return root
        leftAnc = self.lowestCommonAncestor(root.left, p, q)
        rightAnc = self.lowestCommonAncestor(root.right, p, q)
        # 在左子树中没找到，那就是在右子树中
        if not leftAnc:
            return rightAnc
        # 在右子树中没找到，那就是在左子树中
        if not rightAnc:
            return leftAnc
        # 不在左右子树上
        return root
        # @lc code=end
